class Solution {
    vector<int> tmp;
public:
    int reversePairs(vector<int>& record) {
        int n=record.size();
        tmp.resize(n);
        return mergeSort(record,0,n-1);
    }

    int mergeSort(vector<int>& record,int left,int right)
    {
        if(left>=right) return 0;

        int ret=0;
        int mid=(left+right)/2;

        ret+=mergeSort(record,left,mid);
        ret+=mergeSort(record,mid+1,right);

        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=right)
        {
           if(record[cur1]<=record[cur2])
           {
            tmp[i++]=record[cur1++];
           }
           else
           {
            ret+=mid-cur1+1;
            tmp[i++]=record[cur2++];
           }
        }
        while(cur1<=mid)
        {
            tmp[i++]=record[cur1++];
        }
        while(cur2<=right)
        {
            tmp[i++]=record[cur2++];
        }

        for(int i=left;i<=right;i++)
        {
            record[i]=tmp[i-left];
        }

        return ret;
    }

};